package com.lss.c_slidingWindow;

import java.util.*;

/**
 * @author lss
 * @description 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * @createDate 2024/12/2-21:16
 */
public class lc_438 {
    public static void main(String[] args) {

    }

    /**
     * 定长滑动窗口
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams01(String s, String p) {
        List<Integer> list = new ArrayList<>();
        //初始化cP and cS
        int[] cP = new int[26];
        for (int i = 0; i < p.length(); i++) {
            cP[p.charAt(i) - 'a']++;
        }
        int[] cS = new int[26];

        for (int i = 0; i < s.length(); i++) {
            cS[s.charAt(i) - 'a']++;
            //窗口启动
            int left = i - p.length() + 1;
            if (left < 0) {
                continue;
            }
            if (Arrays.equals(cS, cP)) {
                list.add(left);
            }
            cS[s.charAt(left) - 'a']--;
        }
        return list;
    }


    /**
     * 不定长滑动窗口
     * 前提条件在一个窗口内的统计个数相同 and 元素相同则是异构词
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams02(String s, String p) {
        List<Integer> list = new ArrayList<>();
        //初始化cP and cS
        int[] cP = new int[26];
        for (int i = 0; i < p.length(); i++) {
            cP[p.charAt(i) - 'a']++;
        }
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            cP[c]--;
            //窗口启动
            while (cP[c] < 0) {
                cP[s.charAt(left) - 'a']++;
                left++;
            }
            if (i - left + 1 == p.length()) {
                list.add(left);
            }
        }
        return list;
    }

    public List<Integer> findAnagrams_error(String s, String p) {
        char[] chars = p.toCharArray();
        Set<Character> set = new HashSet<>(p.length());
        for (char c : chars) {
            set.add(c);
        }
        int left = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                set.remove(s.charAt(i));
                left = i;
                for (int j = left + 1; (j < left + p.length()) && j < s.length(); j++) {
                    if (set.contains(s.charAt(j))) {
                        set.remove(s.charAt(j));
                    }
                }

                if (!set.isEmpty()) {
                    for (char c : chars) {
                        set.add(c);
                    }

                } else {
                    list.add(left);
                    for (char c : chars) {
                        set.add(c);
                    }
                }
            }

        }
        return list;
    }
}
